package com.yvon.service.demo.algorithm.offer;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 包含min函数的栈
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9830.%20%E5%8C%85%E5%90%ABmin%E5%87%BD%E6%95%B0%E7%9A%84%E6%A0%88/README
 */
public class P30 {

    public static void main(String[] args) {
        MinStack minStack = new P30().new MinStack();
        minStack.push(5);
        System.out.println("最小值：" + minStack.min());
        System.out.println("最新值：" + minStack.top());
        minStack.push(3);
        System.out.println("最小值：" + minStack.min());
        System.out.println("最新值：" + minStack.top());
        minStack.push(6);
        System.out.println("最小值：" + minStack.min());
        System.out.println("最新值：" + minStack.top());
        minStack.push(4);
        System.out.println("最小值：" + minStack.min());
        System.out.println("最新值：" + minStack.top());
        minStack.push(2);
        System.out.println("最小值：" + minStack.min());
        System.out.println("最新值：" + minStack.top());
        minStack.push(3);
        System.out.println("最小值：" + minStack.min());
        System.out.println("最新值：" + minStack.top());
        minStack.push(1);
        System.out.println("最小值：" + minStack.min());
        System.out.println("最新值：" + minStack.top());

    }

    /**
     * 首先定义一个Integer类型的栈，记为stack，此栈用来完成数据正常的push（）、pop（）、top（）和peek（）等操作。
     * 　　然后定义一个Integer类型的栈，记为minStack（一定要理解清楚此栈的作用），此栈主要用来记录每一次stack进行push、pop、top和peek等操作后stack栈中的最小元素，
     *      所以stack的每一次push或者pop操作后，都需要对minStack进行更新处理，以保证minStack能够及时记录stack当前元素中的最小值（stack和minStack需要进行同步操作，
     *      也即stack有元素入栈时候，minStack也要入栈一个特殊的元素（以更新stack中新的最小值）；
     *      stack出栈时候，minStack也要出栈（以更新记录stack中新的最小值））。
     *      简单说，minStack就是实时记录stack中最小元素值，为了保证实时记录的任务，minStack对于stack的push和pop操作需要作出相应的操作。
     * 　　1、stack入栈时候，minStack需要进行的操作
     * 　　　　 （1）如果入栈元素node比minStack栈顶元素小（此处没有讨论stack为空的情况，如果stack为空，则stack和minStack都入栈node元素）
     * 　　　　　　则在stack入栈后，把入栈元素node也加入到minStack栈顶（保证minStack记录stack当前所有元素中的最小值）
     * 　　　　（2）如果入栈元素node比minStack栈顶元大
     * 　　　　　　此情况说明入栈node后stack中最小值没有变，最小值还是入栈前的最小值，所以node不应该加入到minStack的栈顶，但是minStack仍然需要入栈一个元素，这个元素的大小等于minStack的栈顶元素，
     *           如下代码中所示：“minStack.push(minStack.peek());”。这个比较容易忽略，其实只要想一想minStack的作用就很容易理解。
     * 　　2、stack出栈时候，minStack需要进行的操作
     * 　　　 　stack出栈时，minStack也要出栈，以更新对stack最小值的记录。
     * 　　3、过程模拟
     * 　　　　（1）假设stack连续入栈元素为5，3，6，4，2，3，1，则minStack中先后入栈元素为5，3，3，3，2，2，1。
     * 　　　　（2）在（1）基础上，假设stack先后出栈1，3，2，则minStack先后出栈1，2，2。
     *
     *
     * https://blog.csdn.net/weixin_34163741/article/details/94001553?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_title~default-4-94001553-blog-78484646.pc_relevant_multi_platform_whitelistv1_exp2&spm=1001.2101.3001.4242.3&utm_relevant_index=7
     */
    class MinStack  {
        private Deque<Integer> stack;
        private Deque<Integer> minStack;

        public MinStack  () {
            stack = new ArrayDeque<>();
            minStack = new ArrayDeque<>();
            minStack.push(Integer.MAX_VALUE);
        }

        public void push(int val) {
            stack.push(val);
            minStack.push(Math.min(minStack.peek(), val));
        }

        public void pop() {
            stack.pop();
            minStack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int min() {
            return minStack.peek();
        }


    }
}
